package backtrack;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，\
 * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * @author le
 */
public class SearchCharacter
{

    public static void main(String[] args)
    {

    }


    public boolean exist(char[][] board, String word) {
        int row = board.length;            //获取行数；
        int col = board[0].length;         //获取列数；

        int[][] used = new int[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j]==word.charAt(0)) {
                    used[i][j]=1;
                    if (bfs(board, row, col, i, j, 1,word,used))
                        return true;
                    used[i][j]=0;
                }
            }
        }
        return false;
    }

    private static boolean bfs(char[][] board,int row,int col,int i ,int j,int index,String word,int[][] used){
        if (index==word.length()){
            return true;

        }

        //向左走一步
        if (0<=i && i<row && 1<=j && j<col && board[i][j-1]==word.charAt(index) && used[i][j-1]!=1){
            used[i][j-1]=1;
            if (bfs(board, row, col, i, j-1, index+1, word,used))
                return true;
            used[i][j-1]=0;
        }

        //向右走一步
        if (0<=i && i<row && 0<=j && j<col-1 && board[i][j+1]==word.charAt(index) && used[i][j+1]!=1){

            used[i][j+1]=1;
            if (bfs(board, row, col, i, j + 1, index + 1,word,used))
                return true;
            used[i][j+1]=0;
        }

        //向上走一步
        if (1<=i && i<row && 0<=j && j<col && board[i-1][j]==word.charAt(index) && used[i-1][j]!=1) {

            used[i-1][j]=1;
            if (bfs(board, row, col, i - 1, j, index + 1, word,used))
                return true;
            used[i-1][j]=0;
        }

        //向下走一步
        if (0<=i && i<row-1 && 0<=j && j<col && board[i+1][j]==word.charAt(index) && used[i+1][j]!=1) {

            used[i+1][j]=1;
            if (bfs(board, row, col, i + 1, j, index + 1,word,used))
                return true;
            used[i+1][j]=0;
        }

        return false;
    }

}
